%______________________________________________________
%
%   LaTeX-mall för nybörjare
%
%   Konstruerad av Marcus Bergner, bergner@cs.umu.se
%
%   Vid funderingar titta längst ned i denna fil,
%   eller skicka ett mail
%______________________________________________________
%

% lite inställningar
\documentclass[11pt, titlepage, oneside, a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[swedish]{babel}
\usepackage{amssymb, graphicx, fancyhdr}
\addtolength{\textheight}{20mm}
\addtolength{\voffset}{-5mm}
\renewcommand{\sectionmark}[1]{\markleft{#1}}

% \Section ger mindre spillutrymme, använd dem om du vill
\newcommand{\Section}[1]{\section{#1}\vspace{-8pt}}
\newcommand{\Subsection}[1]{\vspace{-4pt}\subsection{#1}\vspace{-8pt}}
\newcommand{\Subsubsection}[1]{\vspace{-4pt}\subsubsection{#1}\vspace{-8pt}}
	
% appendices, \appitem och \appsubitem är för bilagor
\newcounter{appendixpage}

\newenvironment{appendices}{
	\setcounter{appendixpage}{\arabic{page}}
	\stepcounter{appendixpage}
}

\newcommand{\appitem}[2]{
	\stepcounter{section}
	\addtocontents{toc}{\protect\contentsline{section}{\numberline{\Alph{section}}#1}{\arabic{appendixpage}}}
	\addtocounter{appendixpage}{#2}
}

\newcommand{\appsubitem}[2]{
	\stepcounter{subsection}
	\addtocontents{toc}{\protect\contentsline{subsection}{\numberline{\Alph{section}.\arabic{subsection}}#1}{\arabic{appendixpage}}}
	\addtocounter{appendixpage}{#2}
}

% Ändra de rader som behöver ändras
\def\inst{Datavetenskap}
\def\typeofdoc{Laborationsrapport}
\def\course{Programspråk\\7,5 hp}
\def\pretitle{Laboration 3}
\def\title{SPROL}
\def\name{Rebecka Gulliksson, Mathias Hedström}
\def\username{dv10rgn}
\def\email{\username{}@cs.umu.se, dv10mhm@cs.umu.se}
\def\path{edu/5DV086/lab3}
\def\graders{Marcus Karlsson}


% Om du vill referera till katalogen där dina filer ligger kan du 
% använda \fullpath som kommer att vara "~username/edu..." o.s.v.
\def\fullpath{\raisebox{1pt}{$\scriptstyle \sim$}\username/\path}


% Här brjar själva dokumentet
\begin{document}

	% Skapar framsidan (om den inte duger: gör helt enkelt en egen)
	\begin{titlepage}
		\thispagestyle{empty}
		\begin{large}
			\begin{tabular}{@{}p{\textwidth}@{}}
				\textbf{UMEÅ UNIVERSITET \hfill \today} \\
				\textbf{Institutionen för \inst} \\
				\textbf{\typeofdoc} \\
			\end{tabular}
		\end{large}
		\vspace{10mm}
		\begin{center}
			\LARGE{\pretitle} \\
			\huge{\textbf{\course}}\\
			\vspace{10mm}
			\LARGE{\title} \\
			\vspace{15mm}
			\begin{large}
				\begin{tabular}{ll}
					\textbf{Namn} & \name \\
					\textbf{E-mail} & \texttt{\email} \\
					\textbf{Sökväg} & \texttt{\fullpath} \\
				\end{tabular}
			\end{large}
			\vfill
			\large{\textbf{Handledare}}\\
			\mbox{\large{\graders}}
		\end{center}
	\end{titlepage}


	% Fixar sidfot
	\lfoot{\footnotesize{\name, \email}}
	\rfoot{\footnotesize{\today}}
	\lhead{\sc\footnotesize\title}
	\rhead{\nouppercase{\sc\footnotesize\leftmark}}
	\pagestyle{fancy}
	\renewcommand{\headrulewidth}{0.2pt}
	\renewcommand{\footrulewidth}{0.2pt}

	% Skapar innehållsförteckning.
	% Tänk på att köra latex 2ggr för att uppdatera allt
	\pagenumbering{roman}
	\tableofcontents
	
	% och lägger in en sidbrytning
	\newpage

	\pagenumbering{arabic}

	% I Sverige har vi normalt inget indrag vid nytt stycke
	\setlength{\parindent}{0pt}
	% men däremot lite mellanrum
	\setlength{\parskip}{10pt}

	% Lägger in rubrik (finns \section, men då får man mycket spillutrymme)
	\Section{Problemspecifikation}
		% \emph innebär emphasize, d.v.s. betona eller framhåll -> kursiv stil
		\emph{I detta avsnitt beskrivs syftet med laborationen, krav på lösningen m.m.}

		% lägg in en underrubrik (\subsection -> spillutrymme)
		\Subsection{Problemsammanfattning}
                Givet ett nästan komplett programspråk skulle val och implementation av variabelräckvidd, parameteröverföring samt en primitiv datatyp (med två tillhörande operationer, en binär och en unär) göras.

                Första kombinationen av variabelräckvidd och parameteröverföring bestämdes till \verb!static scope! och \verb!pass-by-value!. I den implementationen används datatypen heltal (\verb!int! i Java) och de två operationerna är \emph{addition} (beteckenat med \verb!.!) samt \emph{unärt minus} (betecknat med $\scriptstyle \sim$). 

                Den andra kombinationen blev följaktligen \verb!dynamic scope! tillsammans med \verb!pass-by-reference!. I implementationen används datatypen strängar (\verb!String! i Java). Operationerna på datatypen bestämdes till \emph{konkatenering} (binär operation, beteckenad med \verb!.!) samt \emph{versal-omvandling} (unär operation som omvandlar varje bokstav i strängen till respektive versal bokstav, betecknad med $\scriptstyle \sim$).

		\Subsection{Originalspecifikation}
			Specifikationen i sin helhet finns på\\
                        \verb!http://www8.cs.umu.se/kurser/5DV086/VT12/info/lab3.html!

			% Nytt stycke skapas när du har en, eller flera, tomma rader
			% någonstans i föregående stycke

	\Section{Åtkomst och användarhandledning}
		\emph{I detta avsnitt beskrivs de filer, med tillhörande sökvägar,
			som ingår i lösningen, samt korta beskrivningar om syftet med
			varje fil. Dessutom beskrivs hur man ska handskas med den
			implementerade lösningen till problemet, i form av instruktioner
			för hur körning och kompilering av lösningen sker.}
	
		\Subsection{Filer som ingår i lösningen}
			I katalogen \texttt{\fullpath/lab3a} finns filerna med den första implementationen och i \texttt{\fullpath/lab3b} finns filerna med den andra implementationen.
			
		\Subsection{Kompilering och körning}
		För att kompilera lösningen måste först generera javakod från \verb!Sprol.jj! med hjälp av kommandot \verb!javacc!. De filer 
		som skapats är av typen .java. Dessa ska tillsammans med resterande java filer, tillhörande programmet, koplieras.

		Om de genererade filerna ligger i samma katalog som lösningen, blir kompileringskomandot \verb!javac *.java!.

		För att köra programmet används kommandot \verb!java Sprol <Sökväg till eget program>!, där sökvägen går till en textfil 
		innehållande ett program skrivet i språket SPROL.
			
	\Section{Algoritmbeskrivning}
		\emph{I detta avsnitt beskrivs de algoritmer som anses som
			icke-triviala i uppgiften.}
		
		\Subsection{Evaluering av uttryck}
                Uttryck evalueras med hjälp av en rekursiv stödfunktion på ett väldigt rättframt sätt. Nedan följer pseudokoden för den stödfunktionen:

                \begin{verbatim}
    function evaluate(Expression e) {
      switch(e.type) {
        case CONSTANT:
          return e.const_value
        case VARIABLE:
          return Stack.getVariable(e.variable_name)
        case BINARY_OPERAND:
          return evaluate(e.left_sub_expr) <op1> evaluate(e.right_sub_expr);
        case UNARY_OPERAND:
          return <op2>evaluate(e.left_sub_expr);
      }   
    }
                \end{verbatim}
                \verb!<op1>! är den binära operator som används för den aktuella datatypen (\verb!+! för både heltal och strängar) och \verb!<op2>! är den unära operatorn för den aktualla datatypen (\verb!-! för heltal, samt metoden \verb!toUpperCase! för strängar).

		\Subsection{Exekvera funktionsanrop}
                Ett funktionsanrop exekveres i två fall:
                \begin{itemize}
                  \item om det inte finns något villkor kopplat till funktionsanropet, eller
                  \item om de två variablerna i villkoret \emph{inte} har samma värde.
                \end{itemize}
                
                Om något av dessa villkor är uppfyllda letar run-time-systemet reda på rätt process med hjälp av rekursiv stödfunktion (se pseudokod nedan). När rätt process hittats skapas referensmiljön för den nya funktionen. 

                Ett nytt \verb!ActRecord! läggs överst på stacken (som då också ser till att sätta upp den statiska längen korrekt). Sedan läggs värdena på alla aktuella parametrar (hämtas från stacken) i variabler med namn motsvarande varje formell parameter. Beroende på om \verb!pass-by-value! eller \verb!pass-by-reference! används så görs antingen en ny minnescell för variabeln eller så används den som redan finns på stacken (för den aktuella parametern). Sist initieras alla lokala variabler för funktionen och även dessa läggs till det aktiva \verb!ActRecord!.

                Funktionen exekveras och när den returnerar plockas det översta \verb!ActRecord! (som tillhör den just färdigexekverade funktionen) bort från stacken.

                \Subsubsection{Hitta rätt process}
                För att hitta rätt process (\verb!static scope! används för processerna) söks bland den anropande processens alla subprocesser. Om ingen process med det sökta namnet hittats fortsätter sökningen i den anropande processens förälder och så vidare.

                \begin{verbatim}
    function findProcess(String name, Proc proc) {
      foreach (Proc p : proc.subprocesses) {
        if (p.name == name) return p;
        if (proc.parent == null) error('The called function don't exist.')
        return findProcess(name, proc.parent);  
      }
    }                    
                \end{verbatim}
                Delar: (kolla villkor)hitta rätt process att anropa, sätt upp stacken (beror på \verb!pass-by-value! eller \verb!pass-by-reference!, exekvering och uppstädning
                
                \Subsection{Hitta variabel - statiskt scope}
                För att hitta rätt variabel på stacken i statiskt scope följs den statiska länken i varje \verb!ActRecord!. Genom att rekursivt söka bakåt i stacken hos varje förälder till den exekverende processen hittas antingen rätt variabel, eller så rapporteras ett fel när den yttersta processen (''main'') är nådd.

                \Subsection{Hitta variabel - dynamiskt scope}
		För att hitta variabler på ett dynsmiskt sätt utnyttjas det faktum att alla \textit{activision records} ligger 
		i ordning i stacken. Detta gör det mycket enkelt att söka dynamist då nästa \verb!actRecord! som ska 
		genomsökas ligger på föregående indexplats.
		
	
	\Section{Lösningens begränsningar}
		\emph{I detta avsnitt beskrivs alla begränsningar som lösningen av
			uppgiften innehåller. Detta innefattar även funna begränsningar
			som strider mot specifikationen.}
		
		Ett flertal metoder i lösningen använder sig av rekursion för att på ett enkelt sätt 
		lösa sina arbetsuppgifter. Dessa kan dra ner prestandan på programmen då mer minne blir nödvändigt 
		än vid en vanlig iterering.

	\Section{Testkörningar}
		\emph{I detta avsnitt visas ett antal tester som utförts med programmet.
			Samtliga tester är kommenterade.}
		
		GLÖM INTE ATT KOMMENTERA TESTER!
		
		\begin{footnotesize}
			\begin{verbatim}
				Utdata kan lämpligtvis återges så här, men tänk på att
				        kommentera dina tester. Lägg märke till att rad-
				brytningarna och mellanslagen bevaras!
			\end{verbatim}
		\end{footnotesize}
\end{document}


% Lite information om hur man arbetar med LaTeX
%-----------------------------------------------
%
% LaTeX-koden kan skrivas med en godtycklig editor.
% För att "kompilera" dokumentet anvnds kommandot latex:
%    bergner@peppar:~/edu/sysprog/lab1> latex rapportmall.tex
% Resultatet blir ett antal filer, bl.a. en som heter rapportmall.dvi.
% Denna fil kan anvndas för att titta hur dokumentet egentligen ser
% ut med hjlp av programmet xdvi:
%    bergner@peppar:~/edu/sysprog/lab1> xdvi rapportmall.dvi &
% Du får då upp ett fönster som visar ditt dokument. Detta fönster
% kommer automatiskt att uppdateras då du ändrar och kompilerar om din
% LaTeX-kod. 
% Nr du anser att din rapport är färdig att skrivas ut anvnder man
% lämpligtvis kommandona dvips och lpr:
%    bergner@peppar:~/edu/sysprog/lab1> dvips -P ma436ps rapportmall.dvi
% Om man vill ha kvar PostScript-filen som dvips genererar kan man göra:
%    bergner@peppar:~/edu/sysprog/lab1> dvips -o rapport.ps rapportmall.dvi
%    bergner@peppar:~/edu/sysprog/lab1> lpr -P ma436ps rapport.ps
% OBS!!! För att innehållsförteckningen och eventuella referenser till
% tabeller och figurer garanterat ska stämma mäste man köra latex 2ggr
% på sitt dokument efter att man har ändrat ngot.
%
%
% Lite information om saker man kan tänkas behöva i sitt arbete med LaTeX
%-------------------------------------------------------------------------
%
% FORMATTERA TEXT
%
% För att formattera text på lite olika sätt kan man använda följande LaTeX-
% kommandon:
%    \textbf{denna text kommer att vara i fetstil}
%    \emph{denna text är viktig (kursiv stil)}
%    \texttt{i denna text blir alla tecken lika breda, som med en skrivmaskin}
%    \textsf{denna text visas med ett typsnitt utan serifer}
%
%
% MATEMATISKA FORMLER
%
% För att typsätta matematiska formler kan man använda:
%    $f(x) = x^2 - 3$, vilket lägger in formeln i texten, eller
%    \begin{displaymath}
%        g(x) = \frac{\sin x}{x}
%    \end{displaymath}, vilket låter formeln visas centrerat på en egen rad
% Om du vill att en formel ska numreras byter du ut displaymath mot equation.
% Det finns massor med matematiska symboler, vilket gör att man behver
% någon liten manual att titta i om man ska konstruera avancerade formler.
% Se slutet på filen för lite råd om var du kan hitta sådana.
%
%
% INFOGA FIGURER
%
% För att infoga en figur kan man göra på följande sätt:
%    \begin{figure}[htb]
%        \includegraphics[scale=0.5, angle=90]{exec_flow.eps}
%        \caption{Detta r bildtexten}
%        \label{EXECFLOW}
%    \end{figure}
% Om man vill referera till denna bild i texten skulle man då skriva enligt:
%    ...i figur \ref{EXECFLOW} kan man se att...
% Några små förklaringar till figurer:
%    [htb] = talar om hur latex ska försöka placera bilden (Here, Top, Bottom)
%            Om du anvnder [!h], innebär det Here!!!
%    scale = kan skala om bilden, om den är skalbar
%    angle = kan rotera bilden
%    exec_flow.eps = filnamnet på bilden. Notera att formatet .EPS används
% För att skapa figurer används lämpligtvis programmet xfig:
%    bergner@peppar:~/edu/sysprog/lab1> xfig &
% Rita (och spara ofta) tills du är klar. Välj sedan "Export" och exportera
% din figur till EPS-format.
% Om man vill kan man använda endast \includegraphics, men det är inte ofta
% man gär det.
%
%
% INFOGA TABELLER
%
% Om man vill skapa en tabell gör man på följande sätt:
%    \begin{table}[htb]
%        \begin{tabular}{|rlp{10cm}|}
%            \hline
%            13 & $17.26$ & En kommentar som kan strcka sig ver flera rader \\
%            \hline
%        \end{tabular}
%        \caption{Tabelltexten...}
%        \label{TBL:MINTABELL}
%    \end{table}
% Om man vill kan man endast använda raderna 2-6, dvs få en tabell utan text
% och nummer. Om man gör på detta vis kommer tabellen alltid att läggas på
% det ställe den skrivs i koden, dvs ungefär samma sak som [!h] -> Here!!!
% Några frklaringar:
%    l, r, c = vänsterjustera, högerjustera eller centrera kolumn
%    p{bredd} = skapa en vänsterjusterad kolumn med en viss bredd
%               kan innehålla flera rader text
%    | = en vertikal linje i tabellen
%    \hline = en horisontell linje i tabellen
%    & = kolumnseparator
%    \\ = radseparator
% Tänk på att tabeller oftast ser bättre ut med ganska få linjer.
%
%
% INFOGA KÄLLKOD ELLER UTDATA FRÅN TESTKRNINGAR
%
% Om man vill infoga källkod eller något annat liknande, t.ex. utdata från
% en testkörning är det bra om LaTeX återger utdatan korrekt, dvs en radbrytning
% betyder en radbrytning och 8 mellanslag på rad betyder 8 mellanslag på rad.
% För att stadkomma detta anvnds:
%    \begin{verbatim}
%        allt som skrivs här återges exakt, med skrivmaskinstypsnitt
%    \end{verbatim}
% Oftast finns det dock bttre verktyg för att skriva ut källkod. Exempel på
% sådana är a2ps, enscript och atp.
%
%
% ÄNDRA STORLEK PÅ TEXT
%
% Om du vill ändra storleken på ett stycke, t.ex. på din nyss infogade
% testkörning omger du stycket med \begin{STORLEK} \end{STORLEK}, där
% STORLEK är någon av:
%    tiny, scriptsize, footnotesize, small, normalsize, large, Large,
%    LARGE, huge, Huge
% Tänk på att inte mixtra för mycket med storlekar bara.
%
%
% SKAPA LISTOR AV OLIKA SLAG
%
% Det är ganska vanligt att man vill rada upp saker på något sätt. För att
% skapa punktlistor används:
%    \begin{itemize}
%        \item Detta är första punkten
%        \item Detta är andra punkten
%    \end{itemize}
% Om man istället vill ha en numrerad lista kan man anvnda enumerate istället
% för itemize. Listor kan anvndas i flera nivåer
%
%
% MER INFORMATION OM LaTeX
%
% Lite blandad information om LaTeX, länkar och annat hittar du på
% http://www.cs.umu.se/~bergner/latex.htm
% En del information om rapportskrivning hittar du på
% http://www.cs.umu.se/~bergner/rapport/
% Det finns massor med information om LaTeX på Internet. Ett litet urval:
% http://www.giss.nasa.gov/latex/
%     är en mycket välfylld sida om LaTeX
% http://wwwinfo.cern.ch/asdoc/WWW/essential/essential.html
%     är en manual som genererats utifrån ett LaTeX-dokument mha latex2html
% http://tex.loria.fr/english/
%     är ett fylligt arkiv av länkar till LaTeX-dokument på Internet
%
% Min personliga favorit är dock manualen "The Not So Short Introduction to
% LaTeX2e", som finns i DVI-format på ~bergner/LaTeX/lshort2e.dvi
% Där står i princip allt man behver veta. Det är bara att använda xdvi och
% titta efter det du söker, vilket oftast finns där.
% Om du, precis som jag, vill kunna leka med många kommandon i LaTeX finns en
% "LaTeX Command Summary" p ~bergner/LaTeX/latexcmds.ps